package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
 * 230. 二叉搜索树中第K小的元素
 * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 * <p>
 * 说明：
 * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
 * 进阶：
 * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
 */
public class LeetCode230 {
    private int index;
    private int res;

    /**
     * 方法一： 递归法 深度优先遍历
     * 时间复杂度：O(n) 树个每个节点都会被访问一次
     * 空间复杂度：O(logn) 栈空间
     */
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return 0;
        kthSmallest(root.left, k);
        if (++index == k) {
            res = root.val;
        }
        kthSmallest(root.right, k);
        return res;
    }

    // TODO: 使用其他方法解决
    public int kthSmallest1(TreeNode root, int k) {
       return 0;
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        // 5,3,6,2,4,null,null,1
        LeetCode230 leetCode230 = new LeetCode230();
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        node1.right = new TreeNode(2);
        root.left = node1;
        root.right = node2;
        System.out.println(leetCode230.kthSmallest(root, 1));
    }
}
